/******************************************************************************

    tree.c

******************************************************************************/

#include "stdio.h"
#include "stdlib.h"
#include "SlkConstants.h"
#include "SlkString.h"
#include "tree.h"

#define FALSE       0 
#define TRUE        1 
// #define PRINTF      printf
#define PRINTF(a,b)

extern double  Attribute;
extern double  Answer;

typedef struct _node  {
    slk_size_t    token;
    float         value;
    struct 
    _node   *parent,        // parent is the lhs of the production
            *child,         // first symbol on rhs of production
            *sibling,       // rest of the parent production is siblings
            *left_sibling;  // to go backwards
} node_t;

typedef struct _stack
{
    node_t  **top ,
            **end ,
             *start [ 256 ];
} stack_t;

PRIVATE 
stack_t      Parse_stack = { Parse_stack.start + 255,
                             Parse_stack.start + 255 };

#undef push 
#undef pop

#define push(n,s) if (s.top > s.start) { *--s.top = n; }\
        else { puts ("tree: stack overflow"); exit(1); }

#define pop(s)   ( s.top < s.end ? *s.top++ : *s.top )

PRIVATE 
node_t    *Root;
PRIVATE 
node_t    *Current;
PRIVATE
int        Display = 0;

// -----------------------------------------------------------------------
// private usage
// -----------------------------------------------------------------------

PRIVATE 
node_t *
make_node ( slk_size_t    token )
{
    register
    node_t    *node;

    node = (node_t *)  calloc ( 1, sizeof ( node_t ) );
    if ( node == NULL ) {
        puts ( "make_node calloc failed\n" );
        exit (1);
    }
    node->token = token;
    if ( token == NUMBER_ ) {
        node->value = Attribute;
    }
    return ( node );
}

PRIVATE 
void    
reduce ( slk_size_t production_number )
{
    register
    slk_size_t   *rhs;
    register
    node_t       *prev = NULL;
    node_t       *child = NULL;
    node_t       *this_child = NULL;
    slk_size_t   *lhs;
    int           length,
                  rhs_length;

    if ( Display ) {
        puts ( SlkGetProductionName ( production_number ) );
    }
    lhs = SlkGetProductionArray ( production_number );
    rhs_length = *lhs - 1;
    ++lhs;
    rhs = lhs + 1;
    for ( length = rhs_length;  length > 0;  --length, ++rhs ) {
        if ( SlkIsAction ( *rhs ) ) {
            continue;                               // skip actions
        }
        prev = make_node ( *rhs );
        this_child = prev;
        for ( --length, ++rhs;  length > 0;  --length, ++rhs ) {
            if ( SlkIsAction ( *rhs ) ) {
                continue;                               // skip actions
            }
            prev->sibling = make_node ( *rhs );
            prev->sibling->left_sibling = prev;
            prev = prev->sibling;
        }
    }
    for (;  prev;  prev = prev->left_sibling ) {
        if ( SlkIsNonterminal ( prev->token ) ) {
            child = pop ( Parse_stack );
            if ( child ) {
                PRINTF ( "pop :   %s\n", SlkGetSymbolName ( child->token ) );
                prev->child = child;
                child->parent = prev;
            } else {
                PRINTF ( "pop :   %s\n", "NULL" );
            }
        }
    }
    if ( this_child ) {
        PRINTF ( "push:   %s\n", SlkGetSymbolName ( this_child->token ) );
    } else {
        PRINTF ( "push:   %s\n", "NULL" );
    }
    push ( this_child, Parse_stack );
    if ( production_number == 1 ) {
        Root = make_node ( *lhs );
        Root->child = this_child;
        this_child->parent = Root;
    }
}

PRIVATE 
node_t *
make_LL_branch ( slk_size_t  production_number )
{
    register
    slk_size_t   *rhs;
    register
    node_t       *prev = NULL;
    node_t       *child = NULL;
    slk_size_t   *lhs;
    int           length,
                  rhs_length;

    lhs = SlkGetProductionArray ( production_number );
    rhs_length = *lhs - 1;
    ++lhs;
    rhs = lhs + 1;
    for ( length = rhs_length;  length > 0;  --length, ++rhs ) {
        if ( SlkIsAction ( *rhs ) ) {
            continue;                               // skip actions
        }
        prev = make_node ( *rhs );
        child = prev;
        for ( --length, ++rhs;  length > 0;  --length, ++rhs ) {
            if ( SlkIsAction ( *rhs ) ) {
                continue;                           // skip actions
            }
            prev->sibling = make_node ( *rhs );
            prev->sibling->left_sibling = prev;
            prev = prev->sibling;
        }
    }
    for (;  prev;  prev = prev->left_sibling ) {
        if ( SlkIsNonterminal ( prev->token ) ) {
            push ( prev, Parse_stack );                 // copy parsing pushes
        }
    }

    return  child;
}

PRIVATE 
void    
predict ( slk_size_t  production_number )
{
    register
    slk_size_t   *lhs;
    node_t       *parent;
    node_t       *child;

    if ( Display ) {
        puts ( SlkGetProductionName ( production_number ) );
    }
    lhs = SlkGetProductionArray ( production_number );
    ++lhs;
    if ( ! Root ) {                                    // first call
        Root = make_node ( *lhs );
        push ( Root, Parse_stack );
    }
    parent = pop ( Parse_stack );
    child = make_LL_branch ( production_number );
    if ( child  &&  parent ) {
        parent->child = child;
        child->parent = parent;
    }
}

PRIVATE 
node_t *
show_expression_r ( node_t   *tree )
{                                            // child == left, sibling == right
    register
    node_t  *child,
            *sibling;

    if ( tree == NULL ) {
        return  NULL;
    }
    if ( SlkIsTerminal ( tree->token ) ) {
        if ( tree->token == NUMBER_ ) {
            printf ( "%.2f ", tree->value );
        } else {
            printf ( "%s ", SlkGetSymbolName ( tree->token ) );
        }
    }
    child = tree->child; 
    if ( child != NULL ) {
        show_expression_r ( child );
        for ( sibling = child->sibling;  sibling;  sibling = sibling->sibling ) {
            show_expression_r ( sibling );
        }
    }
    return   tree;
}

PRIVATE 
void 
show_expression ( void )
{
    show_expression_r ( Root );
    printf ( "= %.2f\n", Answer );
}


PRIVATE 
void 
pre_order ( node_t   *tree )
{
    register
    node_t  *child,
            *sibling;

    if ( tree == NULL ) {
        return;
    }
    printf ( "%s\n", SlkGetSymbolName ( tree->token ) );
    child = tree->child; 
    if ( child != NULL ) {
        pre_order ( child );
        for ( sibling = child->sibling;  sibling;  sibling = sibling->sibling ) {
            pre_order ( sibling );
        }
    }
}

PRIVATE 
void 
show_tree ( void )
{
    pre_order ( Root );
}


PRIVATE 
void 
show_parse_derivation_r ( node_t   *tree )
{
    register
    node_t  *child,
            *sibling;

    if ( tree == NULL ) {
        return;
    }
    printf ( "%s --> ", SlkGetSymbolName ( tree->token ) );
    child = tree->child; 
    if ( child != NULL ) {
        printf ( "%s ", SlkGetSymbolName ( child->token ) );
        for ( sibling = child->sibling;  sibling;  sibling = sibling->sibling ) {
            printf ( "%s ", SlkGetSymbolName ( sibling->token ) );
        }
        putchar ( '\n' );
        if ( SlkIsNonterminal ( child->token ) ) {
            show_parse_derivation_r ( child );
        } 
        for ( sibling = child->sibling;  sibling;  sibling = sibling->sibling ) {
            if ( SlkIsNonterminal ( sibling->token ) ) {
                show_parse_derivation_r ( sibling );
            }
        }
    } else { 
        putchar ( '\n' );
    }
}


PRIVATE 
void 
show_parse_derivation ( void )
{
    show_parse_derivation_r ( Root );
}

PUBLIC
Tree_t
GetTree ( int   display )
{              
    Tree_t  tree = { predict, reduce,
                     show_tree, show_parse_derivation, show_expression };
    Root = NULL;
    Current = NULL;
    Display = display;

    return  tree;
}



